﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;


namespace СityDelivery
{
	internal class Algorithm
	{
		private List<int> orderList = new List<int>();
		private List<int> remain = new List<int>();
		private List<Data.shopsInfo> orderWeights = new List<Data.shopsInfo>();
		public void fillRemainList()
		{
			for (int i = 0; i < Data.Shops.Count; i++)
			{
				remain.Add(Data.Shops[i]);
			}
		}

		/// <summary>
		/// Получает матрицу кротчайших путей пар вершин
		/// </summary>
		/// <param name="connectivityMatrix">Матрица смежности</param>
		/// <returns>Матрица кротчайших путей</returns>
		public float[,] GetShortPaths(float[,] connectivityMatrix)
		{
			int n = (int)Math.Sqrt(connectivityMatrix.Length);

			float[,] paths = new float[n, n];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
				{
					paths[i, j] = Data.ConnectivityMatrix[i, j];
					if (paths[i, j] == 0)
						paths[i, j] = (float)Double.PositiveInfinity;

				}

			for (int k = 0; k < n; k++)
				for (int i = 0; i < n; i++)
					for (int j = 0; j < n; j++)
					{
						if (paths[i, j] >= 0)
						{
							paths[i, j] = Math.Min(paths[i, j], paths[i, k] + paths[k, j]);

						}
					}

			return paths;
		}

		/// <summary>
		/// Получение первоначального порядка обхода на основе жадного алгоритма (метод
		/// ближайшего соседа)
		/// </summary>
		/// <param name="lastShop"></param>
		/// <returns></returns>
		public List<int> GetOrderList(int lastShop)
		{

			int temp = 0;
			int tempIndex = 0;
	
			float min = (float)Double.PositiveInfinity;
			for (int index = 0; index < remain.Count; index++)
			{

				if (Data.paths[lastShop, Data.Shops[index]] < min && Data.Shops[index] != lastShop)
				{
					min = Data.paths[lastShop, Data.Shops[index]];
					temp = Data.Shops[index];
					tempIndex = index;
				}
			}

			lastShop = temp;

			remain.RemoveAt(tempIndex);


			orderList.Add(lastShop);
			orderWeights.Add(Data.shopsInfoList[tempIndex]);

			if (remain.Count != 0)
				GetOrderList(lastShop);

			Data.shopsInfoList = orderWeights;
			return orderList;
		}

		/// <summary>
		/// Составление расписания
		/// </summary>
		/// <param name="order">Первоначальный порядок</param>
		/// <param name="prevShop">Предыдущий магазин в подмене</param>
		public void MakeShedule(List<int> order, int prevShop = -1)
		{
			int _timeFrom = 0;
			int _timeTo = 0;
			float _distance = 0;
			String _from = null;
			String _to = null;
			Data.pathList.Clear();
			float overallTime = Data.startTime;
			float carRemain = 0f;
		
			float carLoad;
	
			Data.pathList.Clear();
			for (int i = 0; i < order.Count; i++)
			{

				float remainWeight = Data.shopsInfoList[i].ShopWeight;


				int count = 0;
				do
				{
					carLoad = carRemain != 0f ? carRemain : Data.weightRestriction;

					if (carRemain > 0)
					{
						_timeFrom = (int)overallTime;
						overallTime += Data.paths[order[i - 1], order[i]] / Data.speed * 1000 / 60;
						_distance = Data.paths[order[i - 1], order[i]];
						_timeTo = (int)overallTime;
						for (int index = 0; index < Data.Shops.Count; index++)
						{
							int item = Data.Shops[index];
							if (item == order[i])
							{
								_to = "Магазин на пересечении улиц: " + Data.nodesList[item].StreetArray[0] + " и " + Data.nodesList[item].StreetArray[1];
							}
							if (item == order[i - 1])
							{
								_from = "Магазин на пересечении улиц: " + Data.nodesList[item].StreetArray[0] + " и " + Data.nodesList[item].StreetArray[1];
							}
						}
						Data.pathList.Add(new Data.pathDescriptionStruct(_timeFrom, _timeTo, _from, _to, _distance));
						if (remainWeight - carRemain > 0)
						{
							remainWeight -= carRemain;
							_timeFrom = (int)overallTime;
							for (int index = 0; index < Data.Shops.Count; index++)
							{
								int item = Data.Shops[index];
								if (item == order[i])
								{
									_from = "Магазин на пересечении улиц: " + Data.nodesList[item].StreetArray[0] + " и " +
										  Data.nodesList[item].StreetArray[1];
									break;
								}

							}
							_to = "Склад";

							_distance = Data.paths[Data.warehouse, order[i]];
							overallTime += Data.paths[Data.warehouse, order[i]] / Data.speed * 1000 / 60;
							_timeTo = (int)overallTime;
							carRemain = 0;
							count++;
							Data.pathList.Add(new Data.pathDescriptionStruct(_timeFrom, _timeTo, _from, _to, _distance));
							continue;
						}
						continue;
					}
					else
					{
						overallTime += 30f; // загрузка
						_timeFrom = (int)overallTime;
						overallTime += Data.paths[Data.warehouse, order[i]] / Data.speed * 1000 / 60; // едем в магазин
						_timeTo = (int)overallTime;

						_from = "Склад";
						_distance = Data.paths[Data.warehouse, order[i]];

						for (int index = 0; index < Data.Shops.Count; index++)
						{
							int item = Data.Shops[index];
							if (item == order[i])
							{
								_to = "Магазин на пересечении улиц: " + Data.nodesList[item].StreetArray[0] + " и " + Data.nodesList[item].StreetArray[1];
								break;
							}
						}


					}

					if (remainWeight - carLoad > 0)
					{
						remainWeight -= carLoad;
						carRemain = 0;
					}
					else
					{
						carRemain = carLoad - remainWeight;
						remainWeight = 0;
					}
					Data.pathList.Add(new Data.pathDescriptionStruct(_timeFrom, _timeTo, _from, _to, _distance));
					overallTime += 30f; // разгрузка

					if (carRemain <= 0)
					{
						_timeFrom = (int)overallTime;
						_distance = Data.paths[order[i], Data.warehouse];
						overallTime += Data.paths[order[i], Data.warehouse] / Data.speed * 1000 / 60;
						_timeTo = (int)overallTime;

						_to = "Склад";
						for (int index = 0; index < Data.Shops.Count; index++)
						{
							int item = Data.Shops[index];
							if (item == order[i])
							{
								_from = "Магазин на пересечении улиц: " + Data.nodesList[item].StreetArray[0] + " и " + Data.nodesList[item].StreetArray[1];
								break;
							}
						}
						Data.pathList.Add(new Data.pathDescriptionStruct(_timeFrom, _timeTo, _from, _to, _distance));
					}

					count++;

				} while (remainWeight > 0);

				if (overallTime > Data.shopsInfoList[i].ShopTime && i == 0)
				{
					MessageBox.Show("Нет решения (в один из магазинов никак не успеть)", "Неудача");
					return;
				}

				else if (overallTime > Data.shopsInfoList[i].ShopTime)
				{
					if (order[i] != prevShop)
					{
						float temp = order[i];
						order[i] = order[i - 1];
						order[i - 1] = (int) temp;

						Data.shopsInfo tempShops = Data.shopsInfoList[i];
						Data.shopsInfoList[i] = Data.shopsInfoList[i - 1];
						;
						Data.shopsInfoList[i] = tempShops;

						prevShop = order[i];

						MakeShedule(order, prevShop);

					}
					else
					{
						MessageBox.Show("Нет решения (невозможно составить график)", "Неудача");
						Data.pathList.Clear();
						return;
					}
				}
			}

		}
	}

}
